class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        #dp[i]表示s[0:i]是否能被拆分
        dp = [False for i in range(len(s) + 1)]
        dp[0] = True
        for i in range(1, len(s)+1):
            for j in range(i-1, -1, -1):
                if s[j:i] in wordDict and dp[j]:
                    dp[i] = True
                    break
        return dp[len(s)]
